/*
https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/submissions/582861822/
600. 不含连续1的非负整数
数位DP
*/


class Solution {
public:
    int findIntegers(int n) {
        // for a integral, max 31 bit (1*31), so max height is 32
        vector<int> dp(33, 0);
        dp[1] = 1;
        dp[2] = 2; 
        for (int i=3;i<=32;i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        int pre=0;
        int ans=0;
        for(int i=30;i>=0;i--) {
            int mask=1<<i;

            if((n&mask)){
                ans+=dp[i+1];
                if(pre==1)
                    break;
                pre=1;
            }else{
                pre=0;
            }
            if(i==0)
                ans++;
        }
        return ans;
    }
    
};
